package 力扣日常刷题.木22一月.第06天0114;

/**
 * @author 帅小伙
 * @date 2022/1/14
 * @description
 * 这个再看一下
 */
public class Demo09回溯中等最大兼容性评分和 {

        int m;      //学生和老师的人数
        int n;      //n个问题
        int [][] score;     //学生和老师的匹配得分
        //-------- 回溯用到的
        boolean [] used;
        int max_;
        int cur;

        public int maxCompatibilitySum(int[][] students, int[][] mentors)
        {
            this.m = students.length;
            this.n = students[0].length;
            this.score = new int [m][m];
            this.used = new boolean [m];
            this.max_ = 0;
            this.cur = 0;

            for (int si = 0; si < m; si ++)
            {
                for (int mj = 0; mj < m; mj ++)
                {
                    int cur_score = 0;
                    for (int ni = 0; ni < n; ni ++)
                        if (students[si][ni] == mentors[mj][ni])
                            cur_score ++;
                    score[si][mj] = cur_score;
                }
            }

            backtrace(0);
            return this.max_;
        }

        public void backtrace(int si)
        {
            if (si == m)
            {
                max_ = Math.max(max_, cur);
                return ;
            }
            for (int mj = 0; mj < m; mj ++)
            {
                if (used[mj] == false)
                {
                    used[mj] = true;
                    cur += score[si][mj];
                    backtrace(si + 1);
                    cur -= score[si][mj];
                    used[mj] = false;
                }
            }
        }


}
